Матроид
Матроид (в дискретной математике и комбинаторике) — структура, которая схватывает сущность понятия «независимость», обобщающего линейную независимость в векторных пространствах. =Формальные определения конечных матроидов (finite matroids)= Существуют десятки эквивалентных способов определения (конечных) матроидов. Здесь приведены одни из самых важных. Нет единственного предпочтительного или привычного определения. В этом отношении матроиды отличаются от многих других математических структур, таких, как группы или топологии. Независимые множества, базы и цепи (Independent sets, bases, and circuits) Одно из наиболее значимых определений даётся в терминах независимости. В этом определении конечный матроид (finite matroid) M — это пара (E,I) , где E — конечное множество, а I — семейство подмножеств E (называемых независимыми множествами (independent sets)) со следующими свойствами: * Пустое множество независимо. (Альтернативно, по крайне мере одно подмножество E независимо.) * Каждое подмножество независимого множества независимо. Это иногда называют наследственным свойством (hereditary property). * Если A и B — два независимых множества и A имеет больше элементов, чем B , то в A существует элемент, который не входит в B , но будучи добавленным к B всё ещё даёт независимое множество. Это иногда называют свойством приращения (augmentation property) или свойством обмена независимого множества (independent set exchange property). Первые два свойства просты, но мотивация, стоящая за третьим свойством, не так очевидна. Примеры в разделах примеров ниже сделают эту мотивацию яснее. Подмножество E , которое не является независимым, называется зависимым (dependent). Максимальное независимое множество — т.е. независимое множество, которое становится зависимым добавлением любого элемента из E — называется базой (basis) для матроида. Основной результат матроидной теории, непосредственно аналогичен известной теореме линейной алгебры, заключается в том, что любые две базы матриода M имеют одинаковое число элементов. Это число называется рангом (rank) матроида M . Цепь (circuit) в матроиде M — это минимальное зависимое подмножество E — т.е. зависимое множество, чьи чистые подмножества все независимы. Несмотря на похожесть на определение базы это понятие не имеет аналогии в классической линейной алгебре. Терминологию, пришедшую из теории графов см. ниже. Зависимые множества, базы, или цепи матроида характеризуют данный матроид полностью. Более того, семейство зависимых множеств, или базы, или цепи каждые имеют простые свойства, которые можно взять в качестве аксиом для матроида. Например, можно определить матроид M как пару (E,B) , где E — конечное множество, как и раньше, а B — семейство подмножеств E , называемых базами, со следующим свойством: * Если A и B — различные базы M и a — элемент A , не принадлежащий B , то существует элемент b , принадлежащий B , такой, что B-b+a — это тоже база. Это свойство иногда называют свойством обмена базами (basis exchange property). Ранговые функции (Rank functions) Если M — матроид на E , а A — подмножество E , то матроид на A может быть определен рассмотрением подмножеств A , независимых если и только если они независимы в M . Это позволяет нам говорить о подматроидах (submatroids) и о ранге произвольного подмножества E . Ранговая функция (rank function) r приписывает натуральное число каждому подмножеству E и имеет следующие свойства: * r(A) \leq |A| для всех подмножеств A \subseteq E . * Если A и B — подмножества E , такие что A \subseteq B , то r(A) \leq r(B) . * Для любых двух подмножеств A и B множества E выполнено: r(A \cup B) + r(A \cap B) \leq r(A) + r(B) . Эти три свойства могут быть использованы как одно из альтернативных определений конечного матроида: независимые множества тогда определяются как такие подмножества A \subseteq E , что r(A) = |A| . Операторы замыкания (Closure operators) Пусть M — матроид на конечном множестве E , определенный как выше. Замыкание (closure) cl(A) подмножества A множества E — это подмножество E , содержащее A и каждый элемент x \in E \setminus A , такое, что существует цепь (circuit) C , содержащее x и содержащаяся в объединении A и \{x\} . Это определяет оператор замыкания из P(E) в P(E) , где P обозначает множество всех подмножеств. Оператор замыкания cl из P(E) в P(E) имеет следующее свойство: * Для всех элементов a, b \in E и всех подмножеств Y, Z множества E , если a принадлежит : cl(Y \cup b) \setminus cl(Y) , то b принадлежит cl(Y \cup a) . Это свойство иногда называют свойством обмена Маклэйна–Штейница (MacLane–Steinitz exchange property). В действительности оператор замыкания может быть взят как еще одно определение матроида – любой оператор замыкания на E с данным свойством определяет матроид на E . =Примеры= Однородный матроид (The uniform matroid) Пусть E — конечное множество и k — натуральное число. Можно определить матроид на E , взяв каждое k -элементное подмножество E в качестве базы. Это известно как однородный матроид ранга (uniform matroid of rank) k . Однородный матроид ранга 2 на n точках называется n -точечной линией ( n -point line). Матроиды из линейной алгебры (Matroids from linear algebra) Матроидная теория развилась главным образом из глубоких исследований свойств независимости и размерности в векторных пространствах. Матроиды из векторных пространства всё ещё главные примеры. Существует два способа представить их. * Если E — произвольное подмножество векторного пространства V , то мы можем определить матроид M на E , взяв в качестве независимых множеств в M те, которые являются линейно независимыми элементами в E . Мы говорим, что множество E представляет (represents) M . Матроиды такого рода называются векторными матроидами (vector matroids). * Матрица A со значениями в поле становится матроидом M на её множестве столбцов. Зависимые множества столбцов в матроиде — это те, которые линейно зависимы как векторы. Этот матроид называется столбцовым матроидом (column matroid) от матрицы A , и говорят, что A представляет (represent) M . Столбцовый матроид — это всего лишь векторный матроид под другим именем, но часто существуют причины предпочесть матричное представление. (Существует одно техническое отличие: столбцовый матроид может иметь различные элементы, которые являются одним и тем же вектором, а векторный матроид, определённый выше не может. Обычно это отличие несущественно и может быть проигнорировано, но допущением для E быть мультимножеством векторов оно можно свести к двум определениям в полном согласии.) Матроид, эквивалентный векторному матроиду, хотя он и может быть представленным другим образом, называется представимым (representable). Если M эквивалентен векторному матроиду над полем F , то говорят, что говорят, что M представимо над (presentable over) F . Например, хотя графический матроид (см. ниже) представлен в терминах графов, он также представим векторами над любым полем. Основная проблема матроидной теории — определить является ли данный матроид представимым над данным полем F . Уитни (Whitney) нашёл одно решение этой проблемы, когда F — поле с двумя элементами (см. «Бинарные матроиды» ниже), но общая ситуация существенно сложнее (famously complicated). Матроиды из теории графов (Matroids from graph theory) Второй оригинальный источник для теории матроидов — теория графов. Каждый конечный граф (или мультиграф (multigraph)) G становится матроидом (gives rise to a matroid) следующим образом: берем в качестве E множество всех ребер в G и считаем множество ребер независимым, если и только если оно не содержит простого цикла (a simple cycle). Такое реберное множество называется лесом (a forest) в теории графов. Это называется циклическим матроидом (the cycle matroid) или графическим матроидом (graphic matroid) от G ; и обычно обозначается M(G) . Произвольный матроид, который эквивалентен циклическому матроиду (мульти)графа, даже если он не представлен в терминах графов, называется графическим матроидом (a graphic matroid). Матроиды, которые являются графическими, охарактеризованы Таттом (Tutte). Графические матроиды обобщены до матроидов из помеченных графов (signed graphs) и усечённых графов (biased graphs). Бинарные матроиды (Binary matroids) Матроид, который является представимым над двухэлементным полем, называется бинарным матроидом (binary matroid). Бинарные матроиды включают графические и регулярные матроиды. Они имеют много красивых свойств таких типов матроида. Уитни (Whitney) и Татт (Tutte) нашли их знаменитые характеризации. Сложение множеств — это симметрическая разность. Следующие свойства матроида M эквивалентны: * M — бинарный матроид. *В M , каждая сумма цепей — это объединение несовместных цепей (Уитни (Whitney)). * M не имеет миноров, которые являются 4-точечными линиями (a four-point line) (Татт (Tutte)). Матроид Фано (The Fano matroid) Матроиды с небольшим числом элементов часто изображают в виде диаграмм. Точки — это элементы основного множества, а кривые «протянуты» через каждую цепь (circuit). Диаграмма показывает 3-ранговый матроид, называемый матроидом Фано (the Fano matroid), пример, который появился в 1935 в основополагающей статье Уитни (Whitney). Название возникло из того факта, что матроид Фано — это проективная плоскость второго порядка, известная как плоскость Фано, чьё координатное поле — это двух-элементное поле. Это означает, что матроид Фано — это векторный матроид, связанный с семью ненулевыми векторами в трехмерном векторном пространстве над полем двух элементов. Из проективной геометрии известно, что матроид Фано непредставим произвольным множеством векторов в вещественном или комплексном векторном пространстве (или в любом векторном пространстве над полем, чьи характеристики отличаются от 2). Дуальные матроиды (Dual matroids) Если M — конечный матроид, то можно определить дуальный матроид (the dual matroid) M^* , взяв то же самое основное множество и называя множество базой в M^* , если и только если его компоненты — базы в M . Не трудно проверить, что M^* — матроид и что дуал дуального матроида M^* совпадает с M . Дуал может быть описан эквивалентно хорошим образом в терминах других определений матроида. Например: * Множество независимо в M^* , если и только если его дополнение перекрывает M . * Множество является цепью дуала M^* , если и только если его дополнение — это коатом в M . * Ранговая функция дуала имеет вид: r^*(S) = |E|- r(M) - |S| + r(S) . Главный результат — это матроидная версия теоремы Куратовского (Kuratowski's theorem): «Дуал графического матроида M — графический матроид, если и только если M — матроид планарного графа «. Результат попроще заключается в том, что дуал векторного матроида, представимый над частичным полем (a particular field) F , представим также и над F . Регулярные матроиды (Regular matroids) Матроид регулярный (regular), если он может быть представлен тотально унимодулярной матрицей (матрицей, чьи квадратные подматрицы все имеют определители, раные 0, 1, или −1). Татт доказал, что следующие три свойства матроида логически эквивалентны: * M регулярен. * M представим над каждым полем. * M не имеет минора, который является 4-точечной линией или плоскостью Фано или её дуалом. Для доказательства он использовал его трудную теорему о гомотопиях. С тех пор были найдены более простые доказательства. Наиболее удивительный результат о регулярных матроидах — это теорема декомпозиции Сеймура (Seymour's decomposition theorem), по которой все регулярные матроиды могут быть построены простым способом из графических матроидов и их дуалов и одного специального матроида. Эта теорема имеет много следствий для линейного программирования включая тотально унимодулярные матрицы. =Базовые конструкции= Пусть M — с основным множеством элементов E , и пусть N — другой матроид на другом основном множестве F . Существуют некоторые стандартные способы конструировать новые матроиды из старых. * Ограничение, сужение (Restriction). Если S — это подмножество E , то ограничение, сужение (the restriction) M на S , обозначаемое (written) M|S , — это матроид на основном множестве S , чьи независимые множества являются такими независимыми множествами матроида M , которые содержатся в S . Его цепи — это цепи матроида M , которые содержатся в S и его ранговая функция — это такая же функция матроида M , суженная на подмножества S . * Сжатие (Contraction). Если T — это подмножество E , то сжатие (the contraction) M посредством T , обозначаемое M/T , — это матроид на основном множестве E-T , чья ранговая функция имеет вид r'(A)=r(A \cup T)-r(T) . * Миноры (Minors). Матроид N , который получается из M последовательностью операций сужения и сжатия, называется минором (a minor) матроида M . Говорят, что M содержит (contains) N как минор (as a minor). * Прямая сумма (Direct sum). Прямая сумма (The direct sum) матроидов M и N — это матроид, чьё основное множество является несовместным объединением E и F , и чьи независимые множества являются несовместными объединениями независимых множеств M и независимых множеств N . * Матроидное объединение (Matroid union). Объединение (The union) M и N — это матроид, чьё основное множество является объединением (не несовместным объединением) E и F , и чьи независимые множества являются такими подмножествами, чьи пересечения и с E и F независимы. Обычно термин «объединение» применяется, когда E = F , но это допущение не существенно. Если E и F несовместны, объединение — это прямая сумма. =Дополнительная терминология= Пусть M — матроид с основным множеством элементов E . * Подмножество множества E перекрывает (spans) M , если его замыкание совпадает с E . Говорят, что множество перекрывает (to span) замкнутое множество K , если его замыкание совпадает с K . * Максимальное замкнутое чистое подмножество E называется коатомом (a coatom), или коточкой (copoint), или гиперплоскостью (hyperplane) матроида M . Эквивалентное определение: Коатом — это подмножество E , которое не перекрывает (does not span) M , но такое, что добавление любого другого элемента делает его перекрывающим множеством. * Элемент, который формирует одноэлементную цепь матроида M называется петлей (loop). * Элемент, который не принадлежит ни одной цепи называется копетлей (a coloop). * Если двухэлементное множество \{f, g\} — цепь матроида M , то f и g параллельны (parallel) в M . * M называется простым (simple), если ни 1-, ни 2-элементное подмножество E не является цепью. * Простой матроид, полученный из M удалением всех петлей и удалением одного элемента из каждой 2-элементной цепи пока не останется ни одной 2-элементной цепи, называется упрощением (a simplification) M . * Матроид, который не может быть записан как прямая сумма двух непустых матроидов, называется связным (connected) или несводимым (irreducible). * Максимальный несводимый подматроид матроида M называется компонентой (a component) матроида M . Литература * Crapo, H., and Rota, G-C. (1970), On the Foundations of Combinatorial Theory: Combinatorial Geometries. M.I.T. Press, Cambridge, Mass. * Oxley, J. (1992), Matroid Theory. Oxford University Press, New York. ISBN 0-19-853563-5. * White, N., ed. (1986), Theory of Matroids. Encyclopedia of Mathematics and its Applications, Vol. 26. Cambridge University Press, Cambridge. * Whitney, H. (1935), "On the abstract properties of linear dependence". American Journal of Mathematics, vol. 57, pp. 509-533. См.также * Хасслер Уитни (Hassler Whitney) * Джиан-Карло Рота (Gian-Carlo Rota) * В. Т. Татт (W. T. Tutte) Внешние ссылки * S. C. Locke: Greedy Algorithms. * Steven R. Pagano: Matroids and Signed Graphs. * Sandra Kingan: Matroid theory. Lots of links. * Klaus Truemper Matroid decomposition. * http://en.wikipedia.org/wiki/Matroid Категория:Комбинаторика Категория:Дискретная математика Категория:Незавершённые статьи по эвентологии